package net.tp.algo.cluster;


import net.tp.algo.graph.*;
import net.tp.struct.unionfind.UnionFind;
import java.util.*;


/**
 * <p>Max spacing K cluster</p>
 *
 * @author Trung Phan
 */
public class Cluster {

    private final UnionFind unionFind;

    private final double minDistance;

    private final int size;

    /**
     * @author Trung Phan
     * @param graph undirected graph
     * @param k number of clusters
     */
    public Cluster(UndirectedGraph graph, int k) {
        int N = graph.order();

        if (k < 1 || k > N) throw new IllegalArgumentException("k is out of bound");

        this.unionFind = new UnionFind(N);

        LinkedList<Graph.Edge> edges = new LinkedList<>();
        for (Graph.Edge edge : graph.edges()) edges.add(edge);

        Collections.sort(edges, (p, q) -> Double.compare(p.weight(), q.weight()));

        int size = N; 
        double minDistance = 0.0;

        for (Graph.Edge edge : edges) {
            int u = edge.either();
            int w = edge.other(u);
            if (!unionFind.connected(u, w)) {
                if (size == k) {
                    minDistance = edge.weight();
                    break;
                }
                else {
                    unionFind.union(u, w);
                    size--;
                }
            }
        }

        this.size = size;
        this.minDistance = minDistance;
    }

    /**
     * The min distance among clusters
     * @return the min distance among clusters
     */
    public double minDistance() {
        return minDistance;
    }

    /**
     * The number of clusters
     * @return the number of clusters
     */
    public int size() {
        return size;
    }

}
